Halftoning refers to the process of converting a continuous tone image, which is composed of gray levels, into a binary image. For color halftoning, the halftoning process is repeated in multiple color planes. Desktop printers, such as laser and ink-jet, rely on the digital halftoning technique to produce the visual illusion of continuous tone images. Besides that, color halftoning is also used in display technology. Other major products that employ halftoning technology are color monitors and flat-panel displays.
Halftoning has a long history. The earliest perfected halftoning technique was the analog halftoning, which was developed in the 1880s for printers. Before the analog halftoning, the predominant technology was the letterpress, which was incapable of printing intermediate tones. The letterpress could only print black and white images. At that time, the continuous-tone monochrome photographs were created by highly skill craftsmen. This process was slow and expensive. The halftoning technology was developed to help newspapers and magazines cheaply reproduce photographs in their publications.
In the early part of the 20th century, photolithography was the dominant halftoning technique. In the photolithography halftoning process, a negative of the continuous photograph is projected through a mesh screen onto a photosensitive plate. The mesh screen is usually a fine woven skill. Bright light passes through holes on fine woven skill to form a large round dot on the plate. Dim light would create a small dot. Light sensitive chemicals coating the plate form a small insoluble dot that varies in size according to the tones of the original photographs. This plate will be used for printing.
Later, the finer woven skill screen was replaced by two glass screens, which are coated by an opaque substance. Mesh of parallel and equidistant lines are scratched on each screen. Lines on the second screen are perpendicular to the lines on the first screen. By varying the number lines per inch, coarse or fine resolutions can be made.
The glass plate mesh was replaced by the processed film. The processed film is placed directly in contact with the unexposed lithography film. This approach allows the contact screen to have direct control of the dot structure, the screen frequency, the dot shape and the screen angle of the halftoning.
Almost a hundred years after the analog halftoning technique was developed, printing technology entered a new area: desktop publishing. The mechanical screening process developed since the nineteenth century was replaced by the digital imagesetter. In digital printers, the halftoning process is performed by the raster image processor (RIP) that converts each pixel in the original image from an intermediate tone directly into a binary dot. The binary output is generated based on the pixel-by-pixel comparison of the original image with an array of thresholds. If the pixel value is greater than the threshold value, it is turned on. Otherwise, it is turned off.
The RIP technology imitated the halftone patterns of the contact screens by employing clustered-dot ordered dithering where the threshold array was small. The array size is typically between 8×8 to 12×12. The threshold array was composed of consecutive thresholds arranged along a spiral path radiating outward from the array center. These arrangements would result in a single cluster of on pixels centered within each cell. It forms a regular grid that varied in size according to tone. These techniques were commonly referred as amplitude modulated (AM) halftoning. Like the contact screens, the result patterns of the AM halftoning vary in their screen frequency, dot shape, and screen angle.
In the 1970s, a new halftoning technique was presented. By maintaining the size of printed dots for all gray levels as individual pixels, the visual illusion of continuous pictures can be created by varying the spacing between the printed dots. This is the reason that the new method earned its name as frequency modulated (FM) halftoning.
In the AM halftoning method, the AM screening increases dot percentage in a pixel by growing the size of a dot according to a predetermined pattern. The amplitude of the dot pattern is modulated. The advantage to AM screening is that the human visual system is efficient in filtering out patterns, and therefore human eyes tend to easily ignore the dot structure of an AM screen.
The main problem with AM screening is that it is poor at recording fine detail and edges in an image. Also, when printing several colors, an image artifact known as moire can occur. Moire is the interference of two or more spatial signals, causing the formation of an interference pattern. The theoretical causes for moire patterns are the same as image formations in holography, except in holography, the interference patterns are desired. Moire patterns are not visually pleasant, and are avoided at all costs in the printing industry.
In the FM halftoning, the FM screening increases dot percentage in a pixel by somewhat randomly turning on another dot. The FM screens, which are completely random, are known as white noise masks. The spacing between dots is modulated. A blue noise mask contains a dot pattern in which dot-to-dot transitions within a pixel occur often. In other words the random dots are somehow correlated to exist in a given area of a pixel. Blue noise masks are useful because the human visual system has lower sensitivity to high frequency signals. This causes human eyes to be less capable of perceiving a blue noise mask. In general, all FM screens are good at retaining fine detail, but the final images made with FM screens tend to appear grainy. A major advantage to the FM screening is that it eliminates moiré.
The FM halftoning, however, also has a drawback. Like the AM halftoning schemes, the FM halftoning quantized each pixel individually independent from its neighbors. According to the dither array but with consecutive thresholds dispersed as much as possible. The problem associated with these early FM techniques is that the resulting halftone images suffered from a periodic structure that added an unnatural appearance.
In 1976,l a revolutionary algorithm was developed to resolve this problem. This technique is known as error diffusion. In this technique, the quantization error, rather than being simply discarded, is used to modulate the value of the next incoming pixel gray level. The primary advantage of this technique is its ability to impart a large number of gray levels in the reproduced image. It performs especially well in the presence of very fine details in the image.
The implementation of error diffusion for color halftoning in embedded systems has some basic problems. First, the color error diffusion halftoning is a computationally intensive process. It requires a fast processing unit. Second, most error diffusion algorithms require large memory for storing diffusion coefficients and diffusion errors. Third, the error diffusion process also requires lot of memory accesses, which in general slows down the performance.
In the past, the halftoning processing has normally been performed by the central processing unit (CPU) of a personal computer (PC). Since most PCs have fast CPUs and large memory, there is no issue when the error diffusion algorithm is processed by the CPU of the PC.
Next generation printers, however, may work independently without a PC. In addition, in wireless communications, next generation mobile phones will be able to transmit images and videos. These mobile phones need high performance processors to process data. Printers and mobile devices, however, have limited resources of power, CPU and memory. Software solutions, such as DSPs, can provide a flexible solution but cannot meet real time constraints.
There is therefore a need to develop an efficient embedded architecture to implement color error diffusion halftoning for stand-alone systems.